package org.czl.gh;

import java.util.ArrayList;
import java.util.List;

public class bin {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(3);
        list.add(4);
        list.add(4);
        list.add(4);
        list.add(8);
        list.add(9);
        System.out.println(lowerBound(list,4));
        System.out.println(lowerBound(list,7));
    }
    public static int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    private static int lowerBound(List<Integer> nums, int target) {
        int left = 0, right = nums.size() - 1; // 开区间 (left, right)
        int ans = 0;
        while (left  <= right) { // 区间不为空
            // 循环不变量：
            // nums[left] < target
            // nums[right] >= target
            int mid = (left + right) >>> 1;
            if (nums.get(mid) <= target) {
                ans = mid;
                left = mid + 1; // 范围缩小到 (mid, right)
            } else {
                right = mid - 1; // 范围缩小到 (left, mid)
            }
        }
        return ans;
    }
}
